package leetcode;

//矩阵中的路径
public class Exist {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0;i < board.length;i++){
            for(int j = 0; j < board[0].length;j++){
                if(dfs(board,words,i,j,0)){//找到了返回ture 结束循环，否则继续找
                    return true;
                }
            }
        }
        return false;//最终没有找到返回false
    }
    public boolean dfs(char[][] board,char[] words,int i,int j,int k){
        if(i>= board.length || i<0 || j>board[0].length || j<0 || board[i][j] != words[k]){
            return false;//达到边界或不匹配返回false 回溯 匹配就继续查找 下面的k+1
        }
        board[i][j] = '\0';//将访问过的置为空字符
        if(k == words.length -1){
            return true;//匹配完毕 返回true;
        }
        //下上右左匹配 匹配找到了对应索引的值k+1
        boolean res = dfs(board,words,i+1,j,k+1) || dfs(board,words,i-1,j,k+1)
                || dfs(board,words,i,j-1,k+1) || dfs(board,words,i,j+1,k+1);
        //还原找过的元素，因为之后还可能会遇到(不同路径)
        board[i][j] = words[k];
        return res;//返回是否匹配成功
    }
}
